package second.codeTop.package1;

/**
 * @ClassName LC215
 * @description: 数组中的第K个最大的元素
 * @author: 荣燊
 * @create: 2022-03-04 13:52
 **/
public class LC215 {
    public static void main(String[] args) {
        int[] a = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        int k = 2;
        System.out.println(findKthLargest(a, k));
    }

    // 排序
    public static int findKthLargest(int[] nums, int k) {
        quickSort(nums, 0, nums.length-1);
        return nums[nums.length-k];
    }

    // 快速排序
    public static int partition(int[] nums, int i, int j) {
        int x = i;
        int y = j;
        int temp = nums[i];
        while (x < y) {
            while (x < y && nums[y] >= temp) {
                y--;
            }
            swap(nums, x, y);
            while (x < y && nums[x] < temp) {
                x++;
            }
            swap(nums, x, y);
        }
        return x;
    }

    public static void quickSort(int[] nums, int left, int right) {
        if (left < right) {
            int partition = partition(nums, left, right);
            quickSort(nums, left, partition);
            quickSort(nums, partition+1, right);
        }
    }


    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
